Bounded colorings of graphs and hypergraphs
Jan Volec


Abstract

A conjecture of Bollobas and Erdos from 1976 states that any coloring of edges
of an n-vertex complete graph such that at each vertex no color appears more
than (n/2)-times contains a properly-colored Hamilton cycle. This problem was
a motivation for the following more general question: Let c be a coloring of
E(K_n) where at each vertex, no color appear more than k-times. What properly
colored subgraphs does c necessarily contain?

In this talk, we will be interested in spanning subgraphs of K_n that has bounded
maximum degree or the total number of cherries, i.e., the paths on three vertices.
We will also mention similar questions for hypergraphs, as well as analogous
problems concerned with rainbow subgraphs in edge colorings of K_n, where the
total number of appearances for each color is bounded.

One of our main results confirms the following conjecture of Shearer from 1979:
If G is an n-vertex graph with O(n) cherries and c a coloring of E(K_n) such that
at each vertex every color appears only constantly many times, then c contains a
properly colored copy of G.

The talk is based on a joint work with Nina Kamčev and Benny Sudakov.